package code;

import java.util.HashSet;
import java.util.Random;
import java.util.Set;


public class LongestConsecutive {

	/*
	 * ����Ŀ���
	 */
	public void quickSort(int[] num,int l,int r){
		if(l<r){
			int low=l;
			int high=r;
			int key=num[l];
			while(low<high){
				while(low<high && num[high]>=key)
					high--;
				num[low]=num[high];
				while(low<high && num[low]<key)
					low++;
				num[high]=num[low];
			}
			num[low]=key;
			quickSort(num,l,low-1);
			quickSort(num,l+1,r);
		}
	}
	public int random(int min,int max){
		Random random=new Random();
		int s=random.nextInt(max)%(max-min+1)+min;
		return s;
	}
	/*
	 * ��Ϊ���У�ָ��ֻ����O��n����ʱ�临�Ӷ�
	 * ���Բ�������
	 * ��ô����������ôҪo(1)��ĳ��Ԫ�صĻ���ֻ������hash����
	 * hash��x��
	 * ֮��ȥö��ÿ��Ԫ�أ�����ö�ٵ�ʱ��Ҫ����ѯ���Ԫ��ɾ������ֹ�㷨�˻���O��n^2��
	 */
	public int longestConsecutive(int[] num){
		int n=num.length;
		int i,j;
		Set<Integer> hash=new HashSet<Integer>();
		for(i=0;i<n;i++)
			hash.add(num[i]);
		int ans=0;
		for(i=0;i<n;i++){
			int len=1;
			//����x+��Ԫ��
			for(j=num[i]+1;j-num[i]<n;j++){
				if(!hash.contains(j)){
					break;
				}
				else{
					hash.remove(j);
				}
			}
			len=j-num[i];
			//����x-��Ԫ��
			for(j=num[i]-1;num[i]-j<n;j--){
				if(!hash.contains(j)){
					break;
				}
				else{
					hash.remove(j);
				}
			}
			len+=num[i]-j-1;
			if(ans<len)
				ans=len;
		}
		return ans;
	}
	public static void main(String[] args){
		int[] A={0,-1,1};
		LongestConsecutive lc=new LongestConsecutive();
		System.out.println(lc.longestConsecutive(A));
	}
}
